package primary.primary0;

import java.util.Deque;
import java.util.LinkedList;

public class S0239滑动窗口最大值 {


    /**
     * 91, 19
     * 在一定区间内，然后只关心最值，这个很容易让人想到单调栈
     * 注意，deque的Frist是最后一个放进去的元素
     * 注意 poll是弹出，peek是看，deque的几个方法容易搞混
     */
    public int[] maxSlidingWindow(int[] nums, int k) {
        // 大底的栈
        Deque<Integer> stack = new LinkedList<>();
        for(int i = 0; i < k; i ++){
            while(stack.peek() != null && stack.peek() < nums[i]){
                stack.pop();
            }
            stack.push(nums[i]);
        }
        int[] res = new int[nums.length - k + 1];
        res[0] = stack.peekLast();
        for(int i = 0; i < nums.length - k; i ++){
            if(nums[i] == stack.peekLast()){
                stack.pollLast();
            }
            while(stack.peek() != null && stack.peek() < nums[i + k]){
                stack.pop();
            }
            stack.push(nums[i + k]);
            res[i + 1] = stack.peekLast();
        }
        return res;
    }

    /**
     * 如果维护最大值和最大值出现的次数，每次最大值次数变0后扫描窗口寻找新的最大值
     * 那么一个递减数组，将会有最大的时间复杂度，m*m
     */
    public int[] maxSlidingWindow0(int[] nums, int k) {

        return null;
    }
}
